Farmer John has been elected mayor of
his town! One of his campaign promises was to bring internet connectivity to
all farms in the area. He needs your help, of course.
Farmer John ordered a high speed
connection for his farm and is going to share his connectivity with the other
farmers. To minimize cost, he wants to lay the minimum amount of optical fiber
to connect his farm to all the other farms.
Given a list of how much fiber it
takes to connect each pair of farms, you must find the minimum amount of fiber
needed to connect them all together. Each farm must connect to some other farm
such that a packet can flow from any one farm to any other farm.
The distance between any two farms
will not exceed 100000.
Input. The input
includes several cases. For each case, the first line contains the number of
farms n (3 ≤ n ≤ 100). The following lines contain the n x n
conectivity matrix, where each element shows the distance from on farm to
another. Logically, they are n lines of n space-separated integers. Physically, they are limited
in length to 80 characters, so some lines continue onto others. Of course, the
diagonal will be 0, since the distance from farm i to itself is not interesting
for this problem.
Output. For each
case, output a single integer length that is the sum of the minimum length of
fiber required to connect the entire set of farms.
|
Sample input |
Sample output |
|
4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16
0 |
28 |
графы – минимальный остов –
алгоритм Прима
Поскольку
граф полный, воспользуемся алгоритмом Прима для нахождения минимального
остовного дерева.
Реализация алгоритма
#include <stdio.h>
#include <math.h>
#include <string.h>
#define MAX 110
int m[MAX][MAX];
int i, j, v, dist, to, n;
int used[MAX], min_e[MAX], end_e[MAX];
int main(void)
{
while(scanf("%d",&n)
== 1)
{
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
scanf("%d",&m[i][j]);
memset(min_e,0x3F,sizeof(min_e));
memset(end_e,-1,sizeof(end_e));
memset(used,0,sizeof(used));
dist = min_e[0] =
0;
for (i = 0; i < n; i++)
{
v = -1;
for (j = 0; j < n; j++)
if (!used[j] && (v == -1 || min_e[j] <
min_e[v])) v = j;
used[v] = 1;
if (end_e[v] != -1) dist += m[end_e[v]][v];
for (to = 0; to < n; to++)
{
int dV_TO = m[v][to];
if (!used[to] && (dV_TO < min_e[to]))
{
min_e[to] =
dV_TO;
end_e[to] =
v;
}
}
}
printf("%d\n",dist);
}
return 0;
}
Реализация алгоритма – с одним массивом dist
На каждой итерации ищем вершину cur среди еще не включенных в минимальный остов с минимальным
значением dist[cur]. Включаем вершину cur в остов. Проводим релаксацию всех ребер,
исходящих из cur. Пусть имеется ребро (cur, to) с весом dV_TO. Если dV_TO <
dist[to], то присвоим dist[to] = dV_TO.
Длина минимального остова равна сумме всех чисел в
массиве dist. При этом восстановить сам остов (какие вершины соединяют ребра
остова) у нас нет возможности.
#include <cstdio>
#include <cmath>
#include <cstring>
#include <numeric>
#define MAX 110
#define INF 2100000000
using namespace
std;
int m[MAX][MAX];
int i, j, cur, to, res, n;
int used[MAX], dist[MAX];
int main(void)
{
while(scanf("%d",&n)
== 1)
{
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
scanf("%d",&m[i][j]);
memset(dist,0x3F,sizeof(dist));
memset(used,0,sizeof(used));
dist[0] = 0;
for (i = 1; i < n; i++)
{
int min = INF;
for (j = 0; j < n; j++)
if (!used[j] && (dist[j] < min))
{
cur = j;
min =
dist[j];
}
used[cur] = 1;
for (to = 0; to < n; to++)
{
int dV_TO = m[cur][to];
if (!used[to] && (dV_TO < dist[to]))
dist[to] =
dV_TO;
}
}
res =
accumulate(dist,dist+n,0);
printf("%d\n",res);
}
return 0;
}